public class code2 {

    // 牛客 top101 表达式求值
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    // 存放操作数
    Stack<Integer> nums = new Stack<Integer>();
    // 存放运算符
    Stack<Character> ops = new Stack<Character>();
    // 维护运算符优先级,数字越大优先级越高
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    public int solve (String s) {
        // write code here
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        // 遍历表达式
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 遇到数字
            if (Character.isDigit(ch)) {
                int num = 0;
                int j = i;
                // 判断是否为多位数
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = s.charAt(j++) - '0' + num * 10;
                }
                // 将数字加入操作数集
                nums.push(num);
                // 下轮循环i应该从数字的后一位开始，即j-1，因为while中j < s.length()时
                // j指向了数字的下一位，如果令i=j，则for过程i++时，i将从数字下下一位开始
                i = j - 1;
                // ops为空，运算符和左括号直接入栈
            }  else if (ops.size() == 0 && ch != ')') {
                ops.push(ch);
            }
            // 遇到左括号直接入栈
            else if (ch == '(') {
                ops.push(ch);
            }
            // 遇到右括号，则计算，运算符出栈（由eval完成），直到遇到栈顶为左括号，并舍弃左右括号。左括号前的运算符
            // 会在eval()中出栈
            else if (ch == ')') {
                while (ops.peek() != '(') {
                    eval();
                }
                ops.pop();
            }
            // 遇到运算符
            else {
                // 运算符栈不为空，且栈顶元素不为左括号且当前运算符优先级不大于栈顶运算符优先级，
                // 则对ops弹栈通过eval()进行运算，ops弹栈由eval计算过程中完成，计算直到栈顶的
                // 运算符优先级小于当前运算符优先级为止，并将当前运算符入栈
                while (ops.size() != 0 && ops.peek() != '(' &&
                        map.get(ops.peek()) >= map.get(ch)) {
                    eval();
                }
                ops.push(ch);
            }
        }
        // 栈中还有运算符时，循环运算至ops为空
        while (ops.size() != 0) {
            eval();
        }
        // 最后栈中只剩下计算结果，直接弹栈
        return nums.pop();
    }

    // 计算
    public void eval() {
        int b = nums.pop();
        int a = nums.pop();
        char c = ops.pop();
        int res = 0;
        switch (c) {
            case '+':
                res = a + b;
                break;
            case '-':
                res = a - b;
                break;
            case '*':
                res = a * b;
                break;
        }
        nums.push(res);
    }
}
